#include <bits/stdc++.h>
using namespace std;

/*
1007. 行相等的最少多米诺旋转
已解答
中等
相关标签
相关企业
在一排多米诺骨牌中，tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）

我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。

返回能使 tops 中所有值或者 bottoms 中所有值都相同的最小旋转次数。

如果无法做到，返回 -1.

 

示例 1：


输入：tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
输出：2
解释： 
图一表示：在我们旋转之前， tops 和 bottoms 给出的多米诺牌。 
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。 
示例 2：

输入：tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
输出：-1
解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。
 

提示：

2 <= tops.length <= 2 * 104
bottoms.length == tops.length
1 <= tops[i], bottoms[i] <= 6
*/

// 法一
class Solution {
	public:
	int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
		// 检查某个数字 能够使得所有的 tops 或 bottoms 都是这个数字
		auto check = [&](int x) -> int {
			int top_rotate = 0, bottom_rotate = 0, both = 0;
			for (int i = 0; i < tops.size(); ++i) {
				if (tops[i] != x && bottoms[i] != x)    return -1;      // 都不是 直接失败
				else if (tops[i] == x && bottoms[i] == x)   ++both;
				else if (tops[i] == x)   ++top_rotate;
				else if (bottoms[i] == x)   ++bottom_rotate;
			}
			return min(top_rotate, bottom_rotate);  // 生成最小 后续调用
		};

		// 开始的作为目标
		int ans = check(tops[0]);
		if (ans != -1)  return ans;
		return check(bottoms[0]);
	}
};

// 法二
class Solution {
	public:
	int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {

		int n = tops.size();  // 获取顶部和底部数组的大小

		// 处理第一个目标数字 tag1 (假设从 tops[0] 开始)
		int ans1 = 0;  // 旋转次数
		int tag1 = tops[0];  // 假设目标数字是 tops[0]
		
		// 第一个循环：检查能否通过旋转来使得所有的 top 或 bottom 为 tag1
		for (int i = 1; i < n; i++) {
			// 如果当前的 tops[i] 和 tag1 相等，则无需旋转
			if (tops[i] == tag1) {
				continue;
			}
			// 如果当前的 bottoms[i] 和 tag1 相等，则需要旋转底部
			if (bottoms[i] == tag1) {
				ans1++;
				continue;
			}
			// 如果都不等于 tag1，则无法通过旋转获得一致的结果，直接退出
			ans1 = -1;
			break;
		}

		// 第二个循环：检查能否通过旋转来使得所有的 top 或 bottom 为 tag1
		int ans11 = 0;  // 旋转次数
		for (int i = 0; i < n; i++) {
			// 如果当前的 bottoms[i] 和 tag1 相等，则无需旋转
			if (bottoms[i] == tag1) {
				continue;
			}
			// 如果当前的 tops[i] 和 tag1 相等，则需要旋转顶部
			if (tops[i] == tag1) {
				ans11++;
				continue;
			}
			// 如果都不等于 tag1，则无法通过旋转获得一致的结果，直接退出
			ans11 = -1;
			break;
		}

		// 如果 ans1 和 ans11 不为 -1，则表示可以旋转
		if (ans1 != -1) {
			ans1 = min(ans1, n - ans1);  // 选择最小旋转次数
			ans1 = min(ans1, min(ans11, n - ans11));  // 选择最小旋转次数
		}

		// 处理第二个目标数字 tag2 (假设从 bottoms[0] 开始)
		int ans2 = 0;  // 旋转次数
		int tag2 = bottoms[0];  // 假设目标数字是 bottoms[0]

		// 第三个循环：检查能否通过旋转来使得所有的 top 或 bottom 为 tag2
		for (int i = 1; i < n; i++) {
			if (bottoms[i] == tag2) {
				continue;
			}
			if (tops[i] == tag2) {
				ans2++;
				continue;
			}
			ans2 = -1;
			break;
		}

		// 第四个循环：检查能否通过旋转来使得所有的 top 或 bottom 为 tag2
		int ans22 = 0;  // 旋转次数
		for (int i = 0; i < n; i++) {
			if (tops[i] == tag2) {
				continue;
			}
			if (bottoms[i] == tag2) {
				ans22++;
				continue;
			}
			ans22 = -1;
			break;
		}

		// 如果 ans2 和 ans22 不为 -1，则表示可以旋转
		if (ans2 != -1) {
			ans2 = min(ans2, n - ans2);  // 选择最小旋转次数
			ans2 = min(ans2, min(ans22, n - ans22));  // 选择最小旋转次数
		}

		// 最终的结果：
		if (ans1 == -1 && ans2 == -1) {
			return -1;  // 如果都无法通过旋转使得所有面值一致，返回 -1
		}
		if (ans1 == -1) {
			return ans2;  // 如果 ans1 无效，则返回 ans2
		}
		if (ans2 == -1) {
			return ans1;  // 如果 ans2 无效，则返回 ans1
		}
		return min(ans1, ans2);  // 如果两个结果都有效，返回最小的旋转次数
	}
};
	